//<p>给你一个字符串 <code>s</code> 和一个字符串列表 <code>wordDict</code> 作为字典。请你判断是否可以利用字典中出现的单词拼接出 <code>s</code> 。</p>
//
//<p><strong>注意：</strong>不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入:</strong> s = "leetcode", wordDict = ["leet", "code"]
//<strong>输出:</strong> true
//<strong>解释:</strong> 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入:</strong> s = "applepenapple", wordDict = ["apple", "pen"]
//<strong>输出:</strong> true
//<strong>解释:</strong> 返回 true 因为 <code>"</code>applepenapple<code>"</code> 可以由 <code>"</code>apple" "pen" "apple<code>" 拼接成</code>。
//&nbsp;    注意，你可以重复使用字典中的单词。
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入:</strong> s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//<strong>输出:</strong> false
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 &lt;= s.length &lt;= 300</code></li>
//	<li><code>1 &lt;= wordDict.length &lt;= 1000</code></li>
//	<li><code>1 &lt;= wordDict[i].length &lt;= 20</code></li>
//	<li><code>s</code> 和 <code>wordDict[i]</code> 仅有小写英文字母组成</li>
//	<li><code>wordDict</code> 中的所有字符串 <strong>互不相同</strong></li>
//</ul>
//<div><div>Related Topics</div><div><li>字典树</li><li>记忆化搜索</li><li>哈希表</li><li>字符串</li><li>动态规划</li></div></div><br><div><li>👍 1666</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 单词拆分
 * @author DY Rising
 * @date 2022-06-27 16:25:44
 */
public class P139_WordBreak{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P139_WordBreak().new Solution();
        String leetcode = "leetcode";
        System.out.println(leetcode.substring(0,4));
        System.out.println(leetcode.substring(4,8));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
public class Solution {
    /**
     * 改题解答看了教程
     * 整体思路是动态规划，也可以看是分割
     * 以s = "leetcode", wordDict = ["leet", "code"]为例
     * dp = boolean[9], dp[0] = true
     * 当i= 4时，j = 0，此时s.substring(0,4) = leet在wordDict中
     * 此时dp[0] = true, dp[4] = true
     * 当i = 8时，j = 4，此时s.substring(4,8) = leet在wordDict中
     * 此时dp[0] = true, dp[4] = true，dp[8] = true
      * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

//leetcode submit region end(Prohibit modification and deletion)

}
